package com.aqie.medium.stack;

import java.util.Stack;

/**
 * 856 括号的分数
 * () 得 1 分。
 * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 */
public class ScoreOfParentheses {
    /**
     * 1. 1ms
     * @param S
     * @return
     */
    public int scoreOfParentheses(String S) {
        int length=S.length();
        int sum=0, n = 0;

        for(int i=0;i<length;i++) {
            if(S.charAt(i)=='(') {
                if(n==0)
                {
                    n=1;
                } else {
                    n=n<<1;
                }
            } else if(S.charAt(i)==')') {
                if(S.charAt(i-1)=='(') {
                    sum+=n;
                }
                n=n>>1;

            }
        }
        return sum;
    }

    /**
     * 2, 2ms
     * @param S
     * @return
     */
    public int scoreOfParentheses2(String S){
        Stack<Integer> stack = new Stack<>();
        int cur = 0;
        for (char i : S.toCharArray()){
            if (i == '('){
                stack.push(cur);
                cur = 0;
            }else {
                cur += stack.peek() + Math.max(cur, 1);
                stack.pop();
            }
        }
        return cur;
    }
}
